package hashtable;

import java.util.Scanner;

/**
 * @Auther Jun jie Yi
 * @Date 15:19 2021/7/16
 */
public class HashTableDemo {
    public static void main(String[] args) {

        //创建一个Hash表
        HashTab hashTab = new HashTableDemo().new HashTab(7);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add 添加雇员");
            System.out.println("find 查找雇员");
            System.out.println("list 显示雇员");
            System.out.println("exit 推出系统");
            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("输入 id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    Emp emp = new HashTableDemo().new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "find":
                    System.out.println("输入要查找的 id");
                    int id1 = scanner.nextInt();
                    hashTab.findEmpById(id1);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case  "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }

    }

    //创建HashTable管理多条链表
    class HashTab {
        private EmpLinkedList[] empLinkedListArray;
        private int size;
        //初始化
        public HashTab(int size) {
            this.size = size;
            //初始化 EmpLinkedListArray
            empLinkedListArray = new EmpLinkedList[size];
            //初始化每一个链表
            for (int i = 0; i < size; i++) {
                empLinkedListArray[i] = new EmpLinkedList();
            }
        }
        //添加雇员
        public void add(Emp emp) {
            //得到该员工的 id 应该添加到哪一个链表
            int empLinkedListNO = hashFun(emp.id);
            //将 emp 添加到对应的链表中
            empLinkedListArray[empLinkedListNO].add(emp);
        }
        //编写一个散列函数(写法很多)
        public int hashFun(int id) {
            return id % size;
        }
        //遍历所有的链表
        public void list() {
            for (int i = 0; i < size; i++) {
                empLinkedListArray[i].list(i);
            }
        }
        //根据输入的 id 查找雇员
        public void findEmpById(int id) {
            int empLinkedListNO = hashFun(id);
            Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
            if(emp != null) {
                System.out.printf("在 %d 条链表当中找到雇员 id = %d\n", empLinkedListNO, emp.id);
            } else {
                System.out.println("hash表中未找到");
            }
        }
    }

    //构建一个雇员
    class Emp {
        public int id;
        public String name;
        public Emp next;
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }

    //创建一个EmpLinkedList表示链表
    class EmpLinkedList {
        //头指针，执行第一个 Emp，因此我们这个链表的head 是直接指向第一个 Emp
        private Emp head;
        //添加雇员到链表
        //1.id 自增
        public void add(Emp emp) {
            //如果是添加第一个雇员
            if(head == null) {
                head = emp;
                return;
            }
            Emp curEmp = head;
            while (curEmp.next != null) {
                curEmp = curEmp.next;//后移
            }
            //最后直接在末尾挂上 emp 结点
            curEmp.next = emp;
        }

        //遍历链表的信息
        public void list(int no) {
            if (head == null) {
                System.out.println("第 " + no + " 链表为空！");
                return;
            }
            System.out.print("第 " + no + " 链表信息为");
            Emp curEmp = head;
            while (curEmp != null) {
                System.out.printf(" =>id=%d; name=%s", curEmp.id, curEmp.name);
                curEmp = curEmp.next;
            }
            System.out.println();
        }

        //根据 id 查找雇员，没有找到返回空
        public Emp findEmpById(int id) {
            if(head == null) {
                System.out.println("链表为空");
                return null;
            }
            //辅助指针
            Emp curEmp = head;
            while (curEmp.id != id) {
                curEmp = curEmp.next;
                if(curEmp == null) {
                    break;
                }
            }
            return curEmp;
        }
    }
}
